package tarjan;

import java.util.Scanner;
import java.util.Stack;

/*1p305,测试数据，保证不存在重复边和反向边
5 8
1 2 5
1 3 8
3 2 12
3 4 9
3 5 3
4 1 12
4 5 9
5 1 3
*/
//Tarjan有向图强连通分分量
public class SCC {
	//链式前向星保存图数据
	static int maxv = 101;
	static int maxe = 101;
	//头节点数组
	static int[] head = new int[maxv];
	//边集数组
	static Edge[] edge = new Edge[maxe];
	//边数组的下标
	static int cnt = 0;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int m=sc.nextInt();
		//初始化头节点数组
		for(int i=0;i<maxv;i++) {
			head[i] = -1;
		}
		//获取全部边数据
		for(int i=0;i<m;i++) {
			int u = sc.nextInt();
			int v = sc.nextInt();
			int w = sc.nextInt();
			//有向图
			add(u,v,w);
			
		}
		//打印链式前向星图
		for(int i=1;i<=n;i++) {
			System.out.printf("head[%d]:%d",i,head[i]);
			for(int j=head[i];j!=-1;j=edge[j].next) {
				System.out.printf("-->(to:%d,w:%d,next:%d)",edge[j].to,edge[j].w,edge[j].next);
			}
			System.out.printf("\n");
		}
		System.out.println("--------------------");
		
		tarjan_scc(5);
	}
	
	//添加边的方法
	static void add(int u,int v,int w) {
			
		//edge[cnt].to = u;
	    //edge[cnt].w = w;
        //节点前插
        //edge[cnt].next = head[u];
		edge[cnt] = new Edge(v,head[u],w);

		//head[u]更新为当前边的数组下标
		head[u] = cnt;
		//下标加1
		cnt++;
	}
	
	//时间戳
	static int[] dfn = new int[maxv];
	//追溯点
	static int[] low = new int[maxv];
	//计数器
	static int num = 0;
	//是否在栈中
	static boolean[] ins = new boolean[maxv];
	//栈
	static Stack<Integer> s = new Stack<Integer>(); 
	
	//有向图强连通分量(SCC)Tarjan算法
	//u:节点编号
	static void tarjan_scc(int u) {
		num++;
		dfn[u] = num;
		low[u] = num;
		//入栈
		s.push(u);
		//标记为在栈中
		ins[u] = true;
		//遍历该节点的边
		for(int i=head[u];i!=-1;i=edge[i].next) {
			int v = edge[i].to; //连接的点
			if(dfn[v]==0) {//没有访问过的点
				//dfs搜索
				//u为v的父
				tarjan_scc(v);
				//回溯时更新追溯点
				low[u] = Math.min(low[u], low[v]);
			}else if(ins[v]){//在栈中的点
				low[u] = Math.min(low[u], dfn[v]);
			}
		}
		//强连通分量出栈
		if(low[u] == dfn[u]) {
			int v;
			System.out.println("强连通分量：");
			do {
				v = s.pop();
				System.out.println(v);
				ins[v] = false;
			}while(v!=u);
		}
	}

}








